/*
 * PrintAllPaths.cpp
 *
 *  Created on: Jul 8, 2012
 *      Author: jh238d
 */

#include "BSTNode.h"
#include <iostream>
#include <stack>
using namespace std;

void print_path(stack<BSTNode *> s){
	while(!s.empty()){
		cout << s.top()->data << " ";
		s.pop();
	}
	cout << endl;
}

/*Post-order iterative (BFS)*/
void print_all_paths(BSTNode *root){
	if(!root) return;
	stack<BSTNode *> s, output;
	s.push(root);
	BSTNode *prev = NULL;

	while(!s.empty()){
		BSTNode *curr = s.top();
		if(!prev||curr==prev->left||curr==prev->right){
			if(curr->left){
				s.push(curr->left);
			}else if(curr->right){
				s.push(curr->right);
			}else{
				output = s;
				print_path(s); //leaf, print path
				s.pop();
			}
		}else if(curr->left==prev){
			if(curr->right){
				s.push(curr->right);
			}else{
				s.pop();
			}
		}else if(curr->right==prev){
			s.pop();
		}
		prev = curr;
	}
}

/*Print all edge nodes of a complete binary tree anti-clockwise.*/
void print_left_subtree(BSTNode *root, bool print){
	if(!root) return;
	if(print||(root->left==NULL&&root->right==NULL))
		cout<< root->data<< ' ';
	print_left_subtree(root->left, print);
	print_left_subtree(root->right, (print && root->left?false:true));
}

void print_right_subtree(BSTNode *root, bool print){
	if(!root) return;
	print_right_subtree(root->left, (print && root->right?false:true));
	print_right_subtree(root->right, print);
	if(print||(root->left==NULL&&root->right==NULL))
		cout << root->data <<' ';
}

void print_edge_nodes(BSTNode *root){
	if(!root) return;
	cout << root->data << ' ';
	print_left_subtree(root->left, true);
	print_right_subtree(root->right, true);
}

